package binarysearch;

import java.util.Arrays;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: binarysearch
 * @Author: elvis
 * @CreateTime: 2020-06-07 09:03
 * @Description: 寻找重复数
 * 给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
 *
 * 示例 1:
 *
 * 输入: [1,3,4,2,2]
 * 输出: 2
 *
 * 示例 2:
 *
 * 输入: [3,1,3,4,2]
 * 输出: 3
 *
 * 说明：
 *
 *     不能更改原数组（假设数组是只读的）。
 *     只能使用额外的 O(1) 的空间。
 *     时间复杂度小于 O(n2) 。
 *     数组中只有一个重复的数字，但它可能不止重复出现一次。
 */
public class Leetcode287 {

    /**
     * 先排序数组
     * 根据题意　若不存在重复数　则nums[m]==m+1
     * 所以二分查找　nums[m] < m+1 则重复数在左边
     * 否则重复数在右边
     */
    public int findDuplicate(int[] nums) {
        Arrays.sort(nums);
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] < m + 1) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return nums[l];
    }

    /**
     * 快慢指针
     */
    public int findDuplicate2(int[] nums) {
        int slow = 0, fast = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}
